package com.heima.leetcode.practice;

import org.checkerframework.checker.units.qual.min;

import java.util.Arrays;

/**
 * leetcode 62 不同路径
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/6 12:55
 */
public class E62 {

    /**
     * <h3>方法一：递归，会超出时间限制</h3>
     * @param m 行数
     * @param n 列数
     * @return 路径总数
     */
    public int uniquePaths1(int m, int n) {
        // 递归结束条件：m或者n变为1
        if (m == 1 || n == 1){
            return 1;
        }
        // 递的时候算(m-1, n)的路径总数和(m, n-1)的路径总数
        int left = uniquePaths1(m - 1, n);
        int up = uniquePaths1(m, n - 1);
        // 归的时候相加
        return left + up;
    }

    /**
     * <h3>方法二：动态规划，用二维数组</h3>
     * @param m 行数
     * @param n 列数
     * @return 路径总数
     */
    public int uniquePaths2(int m, int n) {
        // 1. 创建二维数组
        int[][] dp = new int[m][n];
        // 2. 填充数组
        // 2.1 初始化
        Arrays.fill(dp[0], 1);
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        // 2.2 填充
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        // 3. 返回
        return dp[m - 1][n - 1];
    }

    /**
     * <h3>方法三：动态规划，用一维数组优化空间占用</h3>
     * @param m 行数
     * @param n 列数
     * @return 路径总数
     */
    public int uniquePaths3(int m, int n) {
        // 1. 创建一维数组dp
        int[] dp = new int[n];
        // 2. 初始化一维数组
        Arrays.fill(dp, 1);
        // 3. 根据目标更新一维数组
        for (int i = 0; i < m - 1; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j - 1] + dp[j];
            }
        }
        // 4. 返回
        return dp[n - 1];
    }

    /**
     * <h3>方法四：排列组合</h3>
     * @param m 行数
     * @param n 列数
     * @return 路径总数
     */
    public int uniquePaths4(int m, int n) {
        // 1 * 2 * 3 * ... * (m + n -2) / (1 * 2 * ... * (m - 1)) * (1 * 2 * ... * (n - 1))
        // 可以发现分子分母都是m + n - 2项

        // 保证最小值是n
        if (m < n){
            int temp = m;
            m = n;
            n = temp;
        }

        // 前面n - 1项都已经约去了，从n项开始
        long result = 1;
        for (int i = n; i <= m + n - 2; i++) {
            result *= i;
            result /= i - n + 1;
        }
        return (int) result;
    }
}
